package com.pairg.adshelper;

import java.util.*;

public class ABB{
	private Node root;
	public ABB(){
		setRoot(null);
	}

	public Node insert(int k){
		if(isEmpty()){
			setRoot(new Node(null, k));
			return getRoot();
		}
			
		return insert(getRoot(),k);
	}
	
	
	private Node insert(Node n, int k) {
		if(n != null){
			if(k < n.getKey()){
				if(n.getLSon() == null){
					n.setLSon(new Node(n,k));
					n = n.getLSon();
				}
				else
					n = insert(n.getLSon(), k);
			}else if(k > n.getKey()){
				if(n.getRSon() == null){
					n.setRSon(new Node(n,k));
					n = n.getRSon();
				}
				else{
					n = insert(n.getRSon(), k);
				}
			}
		}
		
		return n;
	}

	public void printPreOrder(){
		printPreOrder(getRoot());
	}
	
	private void printPreOrder(Node n) {
		if(n != null){
			System.out.print(n.getKey() + " ");
			printPreOrder(n.getLSon());
			printPreOrder(n.getRSon());
		}
	}

	public void printPosOrder(){
		printPosOrder(getRoot());
	}
	
	private void printPosOrder(Node n) {
		if(n != null){
			System.out.print(n.getKey() + " ");
			printPosOrder(n.getLSon());
			printPosOrder(n.getRSon());
		}
	}
	
	public void printInOrder(){
		printInOrder(getRoot());
	}
	
	private void printInOrder(Node n){
		if(n != null){
			printInOrder(n.getLSon());
			System.out.print(n.getKey() + " ");
			printInOrder(n.getRSon());
		}
	}
	
	public void printLevelOrder(){
		if(!isEmpty()){
			Queue<Node> queue = new LinkedList<Node>();
			queue.add(getRoot());
			
			while(!queue.isEmpty()){
				if(queue.element().getLSon() != null)
					queue.add(queue.element().getLSon());
				if(queue.element().getRSon() != null)
					queue.add(queue.element().getRSon());
				System.out.print(queue.remove().getKey() + " ");
			}
		}
	}
	public void printAllPath(){
		if(!isEmpty()){
			Stack<Node> stkA = new Stack<Node>(); //PILHA COM TODOS OS NOS ATE AS FOLHAS
			Stack<Node> stkB = new Stack<Node>(); //PILHA COM OS NOS QUE JA TEVE SEU FILHO DIREITO ADICIONADO NA PILHA stkA
			stkA.push(getRoot());
			while(!stkA.isEmpty()){
				while(stkA.lastElement().getLSon() != null){ // VAI ATE O NO MAIS A ESQUERDA
					stkA.push(stkA.lastElement().getLSon());
				}
				
				if( stkA.lastElement().getRSon() != null){ // DA UM PASSO PARA DIREITA
					stkB.push(stkA.lastElement());
					stkA.push(stkA.lastElement().getRSon());
				}else{ //SE O TOPO DA PILHA stkA FOR UM NO FOLHA
					printStack(stkA);
			        while((!stkA.isEmpty() && stkA.lastElement().getRSon() == null) || (!stkB.isEmpty() && stkA.lastElement() == stkB.lastElement())){
						if(stkA.lastElement() == stkB.lastElement())
							stkB.pop();
						stkA.pop();
					}
			        
			        if(!stkA.isEmpty()){
			        	stkB.push(stkA.lastElement());
						stkA.push(stkA.lastElement().getRSon());
			        }
				}
			}
		}
	}
	private void printStack(Stack<Node> stkA) {
		Iterator<Node> it=stkA.iterator();
		
        while(it.hasNext()){
        	System.out.print(((Node) it.next()).getKey()+ " ");
        }
        System.out.println();
	}

	public int getHeight(){
		int h = 0;
		if(!isEmpty()){
			int lh = getHeight(getRoot().getLSon());
			int rh = getHeight(getRoot().getRSon());
			h = 1 + ((lh>rh) ? lh : rh);
		}
		return h;
	}
	private int getHeight(Node n) {
		int h = 0;
		if(n != null){
			int lh = getHeight(n.getLSon());
			int rh = getHeight(n.getRSon());
			h = 1+ ((lh>rh) ? lh : rh);
		}
		return h;
	}

	public boolean isEmpty(){
		return getRoot() == null;
	}
	
	public Node search(int k){
		Node n = null;
		if(!isEmpty()){
			n = search(getRoot(),k);
		}
		return n;
	}
	
	private Node search(Node n, int k) {
		if(n != null){
			if(k < n.getKey()){
				return search(n.getLSon(),k);
			}else if(k > n.getKey()){
				return search(n.getRSon(),k);
			}else
				return n;
		}
		
		return null;
	}

	public Node remove(int k){
		Node n = search(k);
		if(n != null){
			n = remove(n);
		}
		
		return n;
	}

	public Node remove(Node z) {
		Node x = null, y = null;
		if(z != null){
			if(z.getLSon() == null || z.getRSon() == null)
				y = z;
			else
				y = sucessor(z);
			
			if(y.getLSon() != null)
				x = y.getLSon();
			else
				x = y.getRSon();
			
			if(x != null)
				x.setDad(y.getDad());
			
			if(y.getDad() == null){
				setRoot(x);
			}else if( y == y.getDad().getLSon()){
				y.getDad().setLSon(x);
			}else
				y.getDad().setRSon(x);
			
			if(y!=z){
				z.setKey(y.getKey());
			}
		}
		
		return y;
	}

	public Node sucessor(Node x) {
		Node y = null;
		if(x != null){
			if(x.getRSon() != null)
				y = minimo(x.getRSon());
			else{
				y = x.getDad();
				while(y != null && x == y.getRSon()){
					x = y;
					y = y.getDad();
				}
			}
		}
		return y;
	}

	public Node minimo(Node x) {
		if(x != null){
			while(x.getLSon() != null)
				x = x.getLSon();
		}
		return x;
	}

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}
}
